#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        vector<int> minV;
        for (auto num : nums)
        {
            if (minV.empty() || num > minV.back())
            {
                minV.push_back(num);
                continue;
            }

            // binary search minV[i]<num<min[i+1]
            int start = 0, end = minV.size();
            while (start < end)
            {
                int index = (start + end) / 2;
                if (minV[index] < num)
                {
                    start = index + 1;
                }
                else if (minV[index] > num)
                {
                    end = index;
                }
                else
                {
                    start = end = index;
                    break;
                }
            }
            if (minV[start] != num)
            {
                minV[start] = num;
            }
        }
        return minV.size();
    }
};

int main()
{
    cout << "Code300" << endl;
    Solution s;
    vector<int> nums = {4, 10, 4, 3, 8, 9};
    cout << s.lengthOfLIS(nums) << endl;
    return 0;
}